Garbage collection refers to a type of automatic memory management found in many modern programming languages, including C#, Java, ML and Lisp. If the garbage collection does not include copying of program objects from one location in memory to another location in memory, long-running programs are likely to suffer from a phenomenon known as “memory fragmentation.” Memory fragmentation leads to unnecessarily large memory requirements by programs, whereby programs may run slower or may eventually fail due to running out of available memory. Copying garbage collection counteracts memory fragmentation by copying program objects for the purposes of packing them closer together in memory. As a result, long-running programs such as operating systems, operating system components, and server applications may be saved from running out of available memory.
A large number of garbage collection techniques are in existence. One family of garbage collection techniques generally operates concurrently with the execution of the program whose memory is being reclaimed, and is referred to as concurrent garbage collection. However, existing garbage collectors for multiprocessor environments suffer from at least one of several problems.
One problem is that some garbage collectors employ what is known as a stop-the-world phase, which has a number of drawbacks. More particularly, in the stop-the-world phase, program execution is stopped for the purposes of doing part or all the work of garbage collection. Among other aspects, stopping program execution prevents the programs from modifying memory, which may include the memory allocated to the objects being processed for garbage collection. The duration that program execution is stopped is known as “pause time.” Pause times degrade the user experience of a program, e.g., a pause time of a tenth of a second could cause the loss of two-to-three frames of video replay and a very noticeable pause in an audio signal.
To obtain short pause times, incremental or concurrent collectors have been developed. However, previous collectors suffer from one of the following drawbacks. Either they employ a stop-the-world phase, which hinder high-responsiveness; or they do not relocate objects, which leads to fragmentation in the long run; or they restrict support to a uniprocessor; or they do not support atomic operations, required to synchronize lock-free (non-blocking) algorithms, or they impose unsustainable overheads on memory usage and/or efficiency, or they impose unrealistic constraints on the behavior of user programs (e.g., violate the language semantics), or they impose unsustainable overheads on memory usage, or they rely on the processor having instructions not found in many commonly used machine architectures (e.g., not supported by the Intel x86 or x64 architectures).
In sum, stop-the-world garbage collectors are not acceptable for many applications. At the same time, known real-time highly-responsive collectors restrict real-time guarantees to uni-processor environments only, rely on special hardware, or suffer from one of the drawbacks mentioned above.